{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Shortest Path with K Hops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestPathWithHops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最短路径的 K 次跨越"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给定一个正整数 n ，它表示一个<strong>&nbsp;索引从 0 开始的无向带权连接图</strong> 的节点数，以及一个&nbsp;<strong>索引从 0 开始的二维数组&nbsp;</strong><code>edges</code> ，其中 <code>edges[i] = [ui, vi, wi]</code> 表示节点 <code>ui</code> 和 <code>vi</code> 之间存在权重为 <code>wi</code> 的边。</p>\n",
    "\n",
    "<p>还给定两个节点 <code>s</code> 和 <code>d</code> ，以及一个正整数 <code>k</code> ，你的任务是找到从 s 到 d 的 <strong>最短 </strong>路径，但你可以 <strong>最多</strong> 跨越 <code>k</code> 条边。换句话说，将 <strong>最多</strong> <code>k</code> 条边的权重设为 <code>0</code>，然后找到从 <code>s</code> 到 <code>d</code> 的 <strong>最短</strong> 路径。</p>\n",
    "\n",
    "<p>返回满足给定条件的从 <code>s</code> 到 <code>d</code> 的 <strong>最短</strong> 路径的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[0,1,4],[0,2,2],[2,3,6]], s = 1, d = 3, k = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>在这个例子中，只有一条从节点1（绿色节点）到节点3（红色节点）的路径，即（1-&gt;0-&gt;2-&gt;3），其长度为4 + 2 + 6 = 12。现在我们可以将两条边的权重设为 0，即将蓝色边的权重设为 0，那么路径的长度就变为 0 + 2 + 0 = 2。可以证明 2 是我们在给定条件下能够达到的最小路径长度。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/30/1.jpg\" style=\"width: 170px; height: 171px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 7, edges = [[3,1,9],[3,2,4],[4,0,9],[0,5,6],[3,6,2],[6,0,4],[1,2,4]], s = 4, d = 1, k = 2\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>在这个例子中，有两条从节点4（绿色节点）到节点1（红色节点）的路径，分别是（4-&gt;0-&gt;6-&gt;3-&gt;2-&gt;1）和（4-&gt;0-&gt;6-&gt;3-&gt;1）。第一条路径的长度为 9 + 4 + 2 + 4 + 4 = 23，第二条路径的长度为 9 + 4 + 2 + 9 = 24。现在，如果我们将蓝色边的权重设为 0，那么最短路径的长度就变为 0 + 4 + 2 + 0 = 6。可以证明 6 是我们在给定条件下能够达到的最小路径长度。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/30/2.jpg\" style=\"width: 400px; height: 171px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, edges = [[0,4,2],[0,1,3],[0,2,1],[2,1,4],[1,3,4],[3,4,7]], s = 2, d = 3, k = 1\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>在这个例子中，从节点2（绿色节点）到节点3（红色节点）有4条路径，分别是（2-&gt;1-&gt;3）、（2-&gt;0-&gt;1-&gt;3）、（2-&gt;1-&gt;0-&gt;4-&gt;3）和（2-&gt;0-&gt;4-&gt;3）。前两条路径的长度为4 + 4 = 1 + 3 + 4 = 8，第三条路径的长度为4 + 3 + 2 + 7 = 16，最后一条路径的长度为1 + 2 + 7 = 10。现在，如果我们将蓝色边的权重设为 0，那么最短路径的长度就为1 + 2 + 0 = 3。可以证明在给定条件下，3 是我们能够达到的最小路径长度。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/30/3.jpg\" style=\"width: 300px; height: 296px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>n - 1 &lt;= edges.length &lt;= n * (n - 1) / 2</code></li>\n",
    "\t<li><code>edges[i].length = 3</code></li>\n",
    "\t<li><code>0 &lt;= edges[i][0], edges[i][1] &lt;= n - 1</code></li>\n",
    "\t<li><code>1 &lt;= edges[i][2] &lt;=&nbsp;10<sup>6</sup></code></li>\n",
    "\t<li><code>0 &lt;= s, d, k&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>s != d</code></li>\n",
    "\t<li>输入的生成确保图是 <strong>连通</strong> 的，并且没有 <strong>重复的边</strong> 或 <strong>自环</strong>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-shortest-path-with-k-hops](https://leetcode.cn/problems/find-shortest-path-with-k-hops/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-shortest-path-with-k-hops](https://leetcode.cn/problems/find-shortest-path-with-k-hops/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1,4],[0,2,2],[2,3,6]]\\n1\\n3\\n2', '7\\n[[3,1,9],[3,2,4],[4,0,9],[0,5,6],[3,6,2],[6,0,4],[1,2,4]]\\n4\\n1\\n2', '5\\n[[0,4,2],[0,1,3],[0,2,1],[2,1,4],[1,3,4],[3,4,7]]\\n2\\n3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u,v,w in edges:\n",
    "            g[u].append((v,w))\n",
    "            g[v].append((u,w))\n",
    "        dp = [inf]*n \n",
    "        for _ in range(k+1):\n",
    "            hq = []\n",
    "            ndp = [inf]*n \n",
    "            ndp[s] = 0\n",
    "            for i in range(n):\n",
    "                for j, w in g[i]:\n",
    "                    ndp[i] = min(ndp[i],dp[j])\n",
    "                hq.append((ndp[i],i))\n",
    "            heapify(hq)\n",
    "            while hq:\n",
    "                dist, i = heappop(hq)\n",
    "                if dist > ndp[i]: continue\n",
    "                for j, w in g[i]:\n",
    "                    if dist+w < ndp[j]:\n",
    "                        ndp[j] = dist+w \n",
    "                        heappush(hq,(ndp[j],j))\n",
    "            dp = ndp \n",
    "        return dp[d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        def dijkstra(st):\n",
    "            pq, ok = [(0, 0, st)], set()\n",
    "            dist = [[inf] * (k + 1) for _ in range(n)]\n",
    "            dist[st] = [0] * (k + 1)\n",
    "\n",
    "            while pq:\n",
    "                # i 是到达当前点 u 的重设次数\n",
    "                cd, i, u = heappop(pq)\n",
    "                if cd > dist[u][i]: continue\n",
    "                for v, w in web[u]:\n",
    "                    # 不重设当前边\n",
    "                    if dist[v][i] > dist[u][i] + w:\n",
    "                        dist[v][i] = dist[u][i] + w\n",
    "                        heappush(pq, (dist[v][i], i, v))\n",
    "                    # 重设当前边\n",
    "                    if i + 1 <= k and dist[v][i + 1] > dist[u][i]:\n",
    "                        dist[v][i + 1] = dist[u][i]\n",
    "                        heappush(pq, (dist[v][i + 1], i + 1, v))\n",
    "            return min(dist[d])\n",
    "        \n",
    "        web = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            web[u].append((v, w))\n",
    "            web[v].append((u, w))\n",
    "\n",
    "        return dijkstra(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        def dijkstra(st):\n",
    "            pq, ok = [(0, 0, st)], set()\n",
    "            dist = [[inf] * (k + 1) for _ in range(n)]\n",
    "            dist[st] = [0] * (k + 1)\n",
    "\n",
    "            while pq:\n",
    "                # i 是到达当前点 u 的重设次数\n",
    "                _, i, u = heappop(pq)\n",
    "                for v, w in web[u]:\n",
    "                    # 不重设当前边\n",
    "                    if dist[v][i] > dist[u][i] + w:\n",
    "                        dist[v][i] = dist[u][i] + w\n",
    "                        heappush(pq, (dist[v][i], i, v))\n",
    "                    # 重设当前边\n",
    "                    if i + 1 <= k and dist[v][i + 1] > dist[u][i]:\n",
    "                        dist[v][i + 1] = dist[u][i]\n",
    "                        heappush(pq, (dist[v][i + 1], i + 1, v))\n",
    "            return min(dist[d])\n",
    "        \n",
    "        web = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            web[u].append((v, w))\n",
    "            web[v].append((u, w))\n",
    "\n",
    "        return dijkstra(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from collections import defaultdict,deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :param s:\n",
    "        :param d:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for i in edges:\n",
    "            m1[i[0]].append((i[1],i[2]))\n",
    "            m1[i[1]].append((i[0],i[2]))\n",
    "        used = {}\n",
    "        sd1 = SortedList(key=lambda x:x[0])\n",
    "        sd1.add((0, s, k))\n",
    "        while sd1:\n",
    "            rank, cur, left = sd1.pop(0)\n",
    "            if cur == d:\n",
    "                return rank\n",
    "            if cur not in used:\n",
    "                used[cur] = rank,left\n",
    "            else:\n",
    "\n",
    "                if used[cur][0] <= rank and used[cur][1] >= left:\n",
    "                    continue\n",
    "                v0,v1 = used[cur]\n",
    "                if rank < used[cur][0]:\n",
    "                    v0 = rank\n",
    "                if left > used[cur][1]:\n",
    "                    v1 = left\n",
    "                used[cur] = v0, v1\n",
    "\n",
    "            for i in m1[cur]:\n",
    "                if left > 0:\n",
    "                    sd1.add((rank, i[0], left-1))\n",
    "                sd1.add((rank+i[1], i[0], left))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        dist = [[inf] * (k + 1) for _ in range(n)]\n",
    "        dist[s][0] = 0\n",
    "        pq = [(0, s, 0)]\n",
    "        while pq:\n",
    "            dis, u, t = heappop(pq)\n",
    "            for v, w in g[u]:\n",
    "                if t + 1 <= k and dist[v][t + 1] > dis:\n",
    "                    dist[v][t + 1] = dis\n",
    "                    heappush(pq, (dis, v, t + 1))\n",
    "                if dist[v][t] > dis + w:\n",
    "                    dist[v][t] = dis + w\n",
    "                    heappush(pq, (dis + w, v, t))\n",
    "        return int(min(dist[d]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        dist = [[inf] * (k + 1) for _ in range(n)]\n",
    "        dist[s][0] = 0\n",
    "        pq = [(0, s, 0)]\n",
    "        while pq:\n",
    "            dis, u, t = heappop(pq)\n",
    "            if dist[u][t] < dis:\n",
    "                continue\n",
    "            for v, w in g[u]:\n",
    "                if t + 1 <= k and dist[v][t + 1] > dis:\n",
    "                    dist[v][t + 1] = dis\n",
    "                    heappush(pq, (dis, v, t + 1))\n",
    "                if dist[v][t] > dis + w:\n",
    "                    dist[v][t] = dis + w\n",
    "                    heappush(pq, (dis + w, v, t))\n",
    "        return int(min(dist[d]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            g[u].append((v, w))\n",
    "            g[v].append((u, w))\n",
    "        dist = [[inf] * (k + 1) for _ in range(n)]\n",
    "        dist[s][0] = 0\n",
    "        pq = [(0, s, 0)]\n",
    "        while pq:\n",
    "            dis, u, t = heappop(pq)\n",
    "            for v, w in g[u]:\n",
    "                if t + 1 <= k and dist[v][t + 1] > dis:\n",
    "                    dist[v][t + 1] = dis\n",
    "                    heappush(pq, (dis, v, t + 1))\n",
    "                if dist[v][t] > dis + w:\n",
    "                    dist[v][t] = dis + w\n",
    "                    heappush(pq, (dis + w, v, t))\n",
    "        return int(min(dist[d]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "      g=defaultdict(list)\n",
    "      for x,y,w in edges:\n",
    "        g[x].append((y,w))\n",
    "        g[y].append((x,w))\n",
    "      dp=[[float('inf')]*(k+1) for _ in range(n)]\n",
    "      dp[s][0]=0\n",
    "      q=[(0,s,0)]\n",
    "      while q:\n",
    "        r,x,t = heappop(q)\n",
    "        if x==d:\n",
    "          return r\n",
    "        for y,w in g[x]:\n",
    "          if r+w<dp[y][t]:\n",
    "            dp[y][t]=r+w\n",
    "            heappush(q,(r+w,y,t))\n",
    "          if t<k and r<dp[y][t+1]:\n",
    "            dp[y][t+1]=r\n",
    "            heappush(q,(r,y,t+1))\n",
    "      return -1          \n",
    "          \n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        e = defaultdict(list)\n",
    "        for u,v,w in edges:\n",
    "            e[u].append((v,w))\n",
    "            e[v].append((u,w))\n",
    "        dis = [[inf]*(k+1) for _ in range(n)]\n",
    "        dis[s][0] = 0\n",
    "        h = [[0,s,0]]\n",
    "        ans = inf\n",
    "        while h:\n",
    "            c,cur,cnt = heappop(h)\n",
    "\n",
    "            for nxt,cost in e[cur]:\n",
    "                if cnt + 1 <= k and dis[nxt][cnt + 1] > c:\n",
    "                    dis[nxt][cnt + 1] = c\n",
    "                    heappush(h,[c,nxt,cnt + 1])\n",
    "                nc = cost + c\n",
    "                if dis[nxt][cnt] > nc:\n",
    "                    dis[nxt][cnt] = nc\n",
    "                    heappush(h,[nc,nxt,cnt])\n",
    "        ans = min(dis[d])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        e = defaultdict(list)\n",
    "        for u,v,w in edges:\n",
    "            e[u].append((v,w))\n",
    "            e[v].append((u,w))\n",
    "        dis = [[inf]*(k+1) for _ in range(n)]\n",
    "        dis[s][0] = 0\n",
    "        h = [[0,s,0]]\n",
    "        ans = inf\n",
    "        while h:\n",
    "            c,cur,cnt = heappop(h)\n",
    "            if dis[cur][cnt] < c:\n",
    "                continue\n",
    "            for nxt,cost in e[cur]:\n",
    "                if cnt + 1 <= k and dis[nxt][cnt + 1] > c:\n",
    "                    dis[nxt][cnt + 1] = c\n",
    "                    heappush(h,[c,nxt,cnt + 1])\n",
    "                nc = cost + c\n",
    "                if dis[nxt][cnt] > nc:\n",
    "                    dis[nxt][cnt] = nc\n",
    "                    heappush(h,[nc,nxt,cnt])\n",
    "        ans = min(dis[d])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        e = defaultdict(list)\n",
    "        for u,v,w in edges:\n",
    "            e[u].append((v,w))\n",
    "            e[v].append((u,w))\n",
    "        dis = [[float('inf') for _ in range(k + 1)] for _ in range(n)]\n",
    "        dis[s][0] = 0\n",
    "        h = [[0,s,0]]\n",
    "        ans = float('inf')\n",
    "        while h:\n",
    "            c,cur,cnt = heappop(h)\n",
    "            if dis[cur][cnt] < c:\n",
    "                continue\n",
    "            for nxt,cost in e[cur]:\n",
    "                if cnt + 1 <= k and dis[nxt][cnt + 1] > c:\n",
    "                    dis[nxt][cnt + 1] = c\n",
    "                    heappush(h,[c,nxt,cnt + 1])\n",
    "                nc = cost + c\n",
    "                if dis[nxt][cnt] > nc:\n",
    "                    dis[nxt][cnt] = nc\n",
    "                    heappush(h,[nc,nxt,cnt])\n",
    "        \n",
    "        for i in range(k + 1):\n",
    "            ans = min(ans,dis[d][i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        e = defaultdict(set)\n",
    "        for u,v,w in edges:\n",
    "            e[u].add((v,w))\n",
    "            e[v].add((u,w))\n",
    "        dis = [[float('inf') for _ in range(k + 1)] for _ in range(n)]\n",
    "        dis[s][0] = 0\n",
    "        h = [[0,s,0]]\n",
    "        ans = float('inf')\n",
    "        while h:\n",
    "            c,cur,cnt = heappop(h)\n",
    "            if dis[cur][cnt] < c:\n",
    "                continue\n",
    "            for nxt,cost in e[cur]:\n",
    "                if cnt + 1 <= k and dis[nxt][cnt + 1] > c:\n",
    "                    dis[nxt][cnt + 1] = c\n",
    "                    heappush(h,[c,nxt,cnt + 1])\n",
    "                nc = cost + c\n",
    "                if dis[nxt][cnt] > nc:\n",
    "                    dis[nxt][cnt] = nc\n",
    "                    heappush(h,[nc,nxt,cnt])\n",
    "        \n",
    "        for i in range(k + 1):\n",
    "            ans = min(ans,dis[d][i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, edges: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        con = collections.defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            con[u].append((v, w))\n",
    "            con[v].append((u, w))\n",
    "        heaq = [(0, s, k)]\n",
    "        ref = defaultdict(lambda: float('inf'))\n",
    "        ref[(s, k)] = 0\n",
    "        while heaq:\n",
    "            cost, node, k = heapq.heappop(heaq)\n",
    "            if node == d:\n",
    "                return cost\n",
    "\n",
    "            for v, w in con[node]:\n",
    "                if k > 0:\n",
    "                    if cost < ref[(v, k - 1)]:\n",
    "                        ref[(v, k - 1)] = cost\n",
    "                        heapq.heappush(heaq, (cost, v, k - 1))\n",
    "                if cost + w < ref[(v, k)]:\n",
    "                    ref[(v, k)] = cost + w\n",
    "                    heapq.heappush(heaq, (cost + w, v, k))\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "from sortedcontainers import SortedList\n",
    "import math\n",
    "import heapq \n",
    "from heapq import heappush as push \n",
    "from heapq import heapify as fy\n",
    "from heapq import heappop as pop\n",
    "class Solution:\n",
    "    def shortestPathWithHops(self, n: int, e: List[List[int]], s: int, d: int, k: int) -> int:\n",
    "        g = [[] for j in range(n)]\n",
    "        for x, y, val in e:\n",
    "            g[x].append([y, val])\n",
    "            g[y].append([x, val])\n",
    "        ans = [[10**10]*(k+1) for _ in range(n)] \n",
    "        st = [[0, s, k]] \n",
    "        v = set() \n",
    "        fy(st)\n",
    "        while st:\n",
    "            val, j, num = pop(st) \n",
    "            # if (j, num) not in v:\n",
    "            if val>=ans[j][num]:\n",
    "                continue \n",
    "            if j==d:\n",
    "                return val \n",
    "            if val<ans[j][num]:\n",
    "                ans[j][num] = val \n",
    "            # continue \n",
    "            # if j==d:\n",
    "            #     if val<ans[]:\n",
    "            #         ans = val \n",
    "                # ans = min(ans, val) \n",
    "            # v.add((j, num)) \n",
    "            for i, nval in g[j]:\n",
    "                if (val+nval) < ans[i][num]:\n",
    "                    push(st, [val+nval, i, num]) \n",
    "                if num>0:\n",
    "                    if val<ans[i][num-1]:\n",
    "                        push(st, [val, i, num-1]) \n",
    "        # return min(ans[d])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
